package my.algo.graph;

import java.util.LinkedList;

/**
 * 使用邻接矩阵表示图
 */
public class MGraph {

	private final int nv;
	private int ne;
	private int[][] adj;

	private boolean[] marked;

	public MGraph(int nv) {
		this.nv = nv;
		this.ne = 0;
		adj = new int[nv][nv];
		marked = new boolean[nv];
	}

	public MGraph addEdge(int v, int w) {
		adj[v][w] = 1;
		this.ne++;
		return this;
	}

	/**
	 * 深度优先遍历
	 */
	public void depthFirstSearch(int v) {
		marked[v] = true;
		for (int i = 0; i < adj[v].length; i++) {
			if (1 == adj[v][i] && !marked[i]) {
				System.out.print(i + " ");
				depthFirstSearch(i);
			}
		}
	}

	/**
	 * 广度优先遍历
	 */
	public void breadthFirstSearch(int v) {
		LinkedList<Integer> queue = new LinkedList<>();
		queue.addLast(v);
		marked[v] = true;
		while (!queue.isEmpty()) {
			int p = queue.removeFirst();
			System.out.print(p + " ");
			for (int i = 0; i < adj[p].length; i++) {
				if (0 == adj[p][i] || marked[i]) {
					continue;
				}
				marked[i] = true;
				queue.addLast(i);
			}
		}
	}

	private void print() {
		for (int i = 0; i < adj.length; i++) {
			for (int j = 0; j < adj[i].length; j++)
				System.out.print(adj[i][j]);
			System.out.println();			
		}
	}

	public static void main(String[] args) {
		MGraph graph = new MGraph(6);
		graph.addEdge(0, 1).addEdge(0, 2).addEdge(0, 5);
		graph.addEdge(1, 0);
		graph.addEdge(2, 0).addEdge(2, 3).addEdge(2, 4);
		graph.addEdge(3, 2).addEdge(3, 4).addEdge(3, 5);
		graph.addEdge(4, 2).addEdge(4, 3);
		graph.addEdge(5, 0).addEdge(5, 3);
		graph.print();
		graph.depthFirstSearch(0);
//		graph.breadthFirstSearch(0);
		System.out.println();
	}
}
